如果没有租用机器这一操作,做法同 P2762 太空飞行计划问题,用最大权闭合子图模型解决。
考虑如何在经典方法构造的新图中体现租用机器这一操作。
新图中对于工作和它所需的机器之间的容量为 , 意义即为选择这个工作就必须购买这个机器。
An Ac a day, keeps the doctor away!
如果没有租用机器这一操作,做法同 P2762 太空飞行计划问题,用最大权闭合子图模型解决。
考虑如何在经典方法构造的新图中体现租用机器这一操作。
新图中对于工作和它所需的机器之间的容量为 +∞ , 意义即为选择这个工作就必须购买这个机器。
fi,j:两人分别在房间 i,j 的概率。初始状态 fa,b=1
fi,j=pipjfi,j+(i,u)∈E∑(j,v)∈E∑degu1−pudegv1−pvfu,v
异或的期望不能直接算,对每一位单独考虑。
f[u][0/1]:节点 u 的第 i 位为 0/1 的概率。
注意经过节点 u 的概率不一定为 1 ,所以 f[u][0]+f[u][1] 的值不一定为 1。
每一条边被选中的概率: 2n(n−1)n−1=n2
所以答案为: